#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
	int numDecodings(string s) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		if(s.size() <= 0)
			return 0;

		return solve(s);
	}

	int solve(const string& s){
		vector<int> ways(s.size(),0);
		if(s[s.size()-1] == '0')
			ways[s.size()-1] = 0;
		else
			ways[s.size()-1] = 1;

		for(size_t i = s.size()-1;i>0;i--){
			size_t curIdx = i-1;
			if(s[curIdx] == '0')
				ways[curIdx] = 0;
			else if(s[curIdx] > '2')
				ways[curIdx] = ways[curIdx+1];
			else if(s[curIdx] == '1'){
				ways[curIdx] = ways[curIdx+1];
				if((curIdx+2)<s.size())
					ways[curIdx] += ways[curIdx+2];
				else
					ways[curIdx] += 1;
			}
			else{
				ways[curIdx] = ways[curIdx+1];

				if(s[curIdx+1]<='6'){
					if((curIdx+2)<s.size())
						ways[curIdx] += ways[curIdx+2];
					else
						ways[curIdx] += 1;
				}
			}
		}

		return ways[0];
	}
};
#endif